package com.sali.排序.raw;

import java.util.Arrays;

/**
 * @description:
 * @author: sali
 * @date: 2025/9/14 下午4:31.
 * @version: 1.0
 */
public class raw4_希尔排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 3, 1};
        System.out.println(Arrays.toString(myGetRes(arr)));
    }

    private static int[] myGetRes(int[] arr) {
        int h = 1;
        while ( h < arr.length / 2 ) {
            h = 2 * h;
        }

        while ( h >= 1 ) {
            int sortedIndex = h;
            while ( sortedIndex < arr.length ) {
                for ( int i = sortedIndex; i >= h; i -= h ) {
                    if ( arr[i] < arr[i-h] ) {
                        int temp = arr[i];
                        arr[i] = arr[i-h];
                        arr[i-h] = temp;
                    } else {
                        break;
                    }
                }
                sortedIndex++;
            }
             h /= 2;
        }

        return arr;
    }

}
